package cym;

public class TreeSelectSort {

    public static void sort(int[] r) {
        int len = r.length;
        //根据待排序序列的结点个数，计算胜者树的叶子结点个数，该个数必须是2的幂
        int leafSize = 1;
        while (leafSize < len) {
            leafSize *= 2;
        }
        //计算胜者树的所有节点数，叶子结点存放的起始位置
        int TreeSize = 2 * leafSize - 1;
        int loadIndex = leafSize - 1;

        TreeNode[] tree = new TreeNode[TreeSize];//胜者树结点数组
        //把待排序结点复制到胜者树的叶子结点中,并补足外结点
        int j = 0;
        for (int i = loadIndex; i < TreeSize; i++) {
            tree[i] = new TreeNode();
            tree[i].setIndex(i);
            if (j < len) {
                tree[i].setActive(1);
                tree[i].setData(r[j++]);
            } else {
                tree[i].setActive(0);
            }
        }
        //产生胜者树
        //查找最小结点
        int i = loadIndex;
        while (i > 0) {
            //处理各对比赛者
            j = i;
            while (j < 2 * i) {
                if (tree[j + 1].getActive() == 0 || (tree[j].getData() <= (tree[j + 1].getData()))) {
                    tree[(j - 1) / 2] = tree[j];      //左孩子(胜者)赋值给父结点
                } else {
                    tree[(j - 1) / 2] = tree[j + 1];  //右孩子(胜者)赋值给父结点
                }
                j += 2;     //下一对比赛者
            }
            i = (i - 1) / 2;    //处理上层结点
        }
        //将最小结点存入序列r的第一个位置
        r[0] = tree[0].getData();

        for (i = 1; i < len; i++) {  //处理剩余的n-1个记录
            updateTree(tree, tree[0].getIndex());   //调整胜者树
            r[i] = tree[0].getData();               //将胜者树的根(最小者)存入数组r
        }
    }


    // i是当前最小关键字记录的下标
    private static void updateTree(TreeNode[] tree, int i) {
        tree[i].setActive(0);  //该元素相应外结点不再比赛
        int j;
        if (i % 2 == 0) { //i为偶数，对手为左结点
            tree[(i - 1) / 2] = tree[i - 1];
        } else { //i为奇数，对手为右结点
            tree[(i - 1) / 2] = tree[i + 1];
        }
        i = (i - 1) / 2;   //最小元素输出后，其对手上升到父结点
        while (i > 0) {          //直到i==0
            if (i % 2 == 0) {   //i为偶数，对手为左结点
                j = i - 1;
            } else {            //i为奇数，对手为右结点
                j = i + 1;
            }
            //比赛对手中有一个为空
            if (tree[j].getActive() == 0 || (tree[i].getActive() == 1 && tree[i].getData() <= tree[j].getData())) {
                tree[(i - 1) / 2] = tree[i];
            } else {
                tree[(i - 1) / 2] = tree[j];
            }
            i = (i - 1) / 2;     //i上升到父结点
        }
    }

    public static void display(int[] r) {
        for (int item : r) {
            System.out.print(item + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] r = new int[]{3, 5, 5, 4, 120, 43, 1, 76, 78, 12, 346};
        TreeSelectSort.sort(r);
        TreeSelectSort.display(r);
    }

    static class TreeNode {      //胜者树的结点类

        private int data;         //排序记录结点数据值
        private int index;        //结点在满二叉树中的序号
        private int active;       //参加选择标志，1表示参选，0表示不参选

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public int getActive() {
            return active;
        }

        public void setActive(int active) {
            this.active = active;
        }
    }

}
